\section{Introduction}
``Pac-Man'' is an arcade game that was released in 1980\cite{wiki:pacman}. In the game, the player controls a yellow avatar navigates it through a maze. The maze contains ghosts (enemies), pills (which increase Pac-Man's score when consumed), and power pills (which are worth more points than power pills and render the ghosts consumable for a period of time). Pac-Man begins the game with three lives, and is awarded an extra life for each $10,000$ points that are scored. If Pac-Man remains alive until time expires on a level, the player is awarded points for the pills and power pills that are not consumed, but does not receive the points that would have been awarded for consuming up to four ghosts after activating a power pill \cite{pacman}.

\subsection{Ms. Pac-Man}
While there are several stylistic differences between ``Pac-Man'' and ``Ms. Pac-Man'', what sets ``Ms. Pac-Man'' apart in terms of gameplay is the pseudo-random movement reversal of the ghosts in ``Ms. Pac-Man''. The ghosts in the original ``Pac-Man'' game move predictably. When a ghost begins down a segment of the maze, that ghost will continue until it encounters ``Pac-Man'' or a junction (an intersection where movement is allowed in more than two directions). In ``Ms. Pac-Man'', there is a small probability that a ghost will reverse course in the middle of a path. This pseudo-random behavior prevents players from using patterns in the ghosts' behavior to predict their location well into the future.

Originally, competitions to find the best artificially intelligent ``Ms. Pac-Man'' agent relied on screenshots to determine the state of a game and decide on a move to make. These competitions were run using emulations of the original game, and only had access to the controls for the ``Pac-Man'' agent.

\subsection{Ms. Pac-Man vs Ghosts Competition}
Recently, software has been written that simulates ``Ms. Pac-Man'' in an open-source format. This Java implementation allows for full modification of the game's behavior: from the speed which ``Ms. Pac-Man'' and the ghosts move, to the strategies that both ``Ms. Pac-Man'' and the team of ghosts use to navigate the maze.

Such fine-grained control has given rise to the ``Ms Pac-Man vs Ghosts League'', a competition that matches artificially intelligent ``Ms. Pac-Man'' agents against artificially intelligent ghost teams. Rankings are based on the number of points that ``Ms. Pac-Man'' can score (where the agent attempts to maximize its score and the ghosts attempt to minimize the score of ``Ms. Pac-Man''. The software package include several simple ``Ms. Pac-Man'' agents and ghosts teams that can be compared against. The competition website also archives past entries for testing against new competitors.

In Section~\ref{sec:relatedwork}, we take a look at previous methods that have been designed for ``Ms. Pac-Man''. Section~\ref{sec:representation} explains the method that we employ; Section~\ref{sec:results} describe the results that we obtained, and Section~\ref{sec:futurework} summarizes and analyzes our findings and discusses future work.
